Many data storage devices use microprocessors to execute commands. Typically, a data storage device can accommodate multiple microprocessor commands. For example, the microprocessor in a disc drive device may receive multiple commands to read or write data from or to media within the disc drive. When commands are received in a data storage device faster than the commands can be executed, the commands are typically buffered to await their turn for processing by the microprocessor in the data storage device. Additionally, data associated with a write command is typically held in a cache memory until the associated command is processed.
Performance in a data storage device can often be improved by executing the received commands in an order different from the order they were originally received. Ordering the commands in this manner is called command reordering. Command reordering allows for a more efficient use of the microprocessor as well as a more efficient use of the hardware being controlled by the microprocessor. For instance, a disc drive may receive commands to read and/or write data at a variety of locations on the hard discs within the disc drive. Ideally, these commands would be processed in a manner that would that would optimize user perceived performance.
There are a number of ways to order the commands in a command queue. Traditionally, disc drives have employed algorithms to sort commands in an order that minimizes seek time between the various commands. The seek time is the time required for the read/write element to radially move across or traverse cylinders between a current cylinder over which the read/write element is positioned and a target cylinder to be addressed in response to a particular command. However, seek time is only one of two components of the true access time of a command. Another component is the rotational latency time or the amount of time the disc drive spends waiting for the appropriate data to rotate under the read/write element. The rotational latency time may be a significant part of the total access time. Often, it is the dominant component of the total access time for relatively short seeks. As such, many current command ordering algorithms are optimized to reduce rotational latency, either alone or in conjunction with some form of seek time minimization.
One significant drawback associated with prior command ordering algorithms is that they do not give preference to pending commands in the reordering process. When a pending command is not given preference over non-pending commands, performance of the data storage device suffers. As used herein, a pending command is a command for which the command has not returned status. For example, a read command is pending until the host computer receives the data and status from the disc drive. As another example, a write command is pending until the disc drive notifies the host that the disc drive receives the data and sends completion status to the host. Hence, non-pending commands are those that the host computer perceives as complete, but are not completed in the data storage device.
An example of a non-pending command in the disc drive is a ‘writeback’ command. Frequently, when a disc drive receives a write command, the associated data is not immediately written to the disc, but rather it is cached until the write becomes favorable to commit to the media. When the write data is cached and completion status is sent to the host, the write command becomes a writeback command. Writeback commands are not pending because the host computer has been given notification that the associated data has been received by the disc drive. In other words, from the host computer's perspective, the write command has been completed; however, the disc drive still must execute the writeback command while it is cached.
As noted, traditional reordering algorithms do not give preference to pending commands in the reordering process. That is, these algorithms give the same priority to the pending command(s) as to the non-pending commands. Often the number of buffered non-pending commands exceeds the number of pending commands and the non-pending commands become more favorable to commit to the media. As a result, a pending command, for which the host computer requires prompt processing by the data storage device, may be delayed for a substantial amount of time while non-pending commands are processed. When pending commands are delayed, performance is reduced from the host computer's perspective. In particular, when the processing of pending commands is delayed, a computer user may perceive a lower level of data throughput between the host computer and the disc drive than if the pending commands are not delayed.
There is strong motivation in the industry to improve all aspects of performance, including throughput. Accordingly, there is a continual need for improvements in the art whereby pending commands and non-pending commands are executed in an efficient order while giving preference to pending commands, thereby reducing latency and improving performance.